package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * An implementation of binary heap. Values must be unique. Keys must be
 * Comparable.
 * 
 * @author Dasha Stroganova
 * 
 * @param <V>
 *            value
 * @param <K>
 *            key
 */
public class BinaryHeap<V, K extends Comparable<? super K>> {

	private final List<V> heap;

	private final Map<V, K> valueKeyMap;

	private final Map<V, Integer> valueIndexMap;

	/**
	 * Creates empty binary heap.
	 * 
	 */
	public BinaryHeap() {
		heap = new ArrayList<V>();
		valueKeyMap = new HashMap<V, K>();
		valueIndexMap = new HashMap<V, Integer>();
	}
	
	/**
	 * Returns the number of elements in this binary heap.
	 * 
	 * @return the number of elements in this binary heap.
	 */
	public int size() {
		return heap.size();
	}

	/**
	 * Tests if this binary heap has no elements.
	 * 
	 * @return true if this binary heap has no elements; false otherwise.
	 */
	public boolean isEmpty() {
		return (size() == 0);
	}
	
	/**
	 * Returns key for the given value. Null if given value is not in heap.
	 * 
	 * @param value
	 * @return key
	 */
	public K getKey(V value) {
		return valueKeyMap.get(value);
	}
	
	/**
	 * Inserts the specified value to right place of the heap according to its key. If value is already in heap its key is increased or decreased.
	 *
	 * @param value 
	 * @param key 
	 */
	public void insert(V value, K key) {
		if (valueKeyMap.containsKey(value)) {
			if (valueKeyMap.get(value).compareTo(key) < 0) {
				increaseKey(value, key);
			} else {
				decreaseKey(value, key);
			}
		} else {
			heap.add(value);
			valueIndexMap.put(value, heap.size() - 1);
			valueKeyMap.put(value, key);
			siftUp(heap.size() - 1);
		}
	}
	
	/**
	 * Removes the minimal element of this binary heap and returns it.
	 * 
	 * @return the minimal element of the binary heap.
	 */
	public V extractMin() {
		if (isEmpty()) {
			return null;
		}
		V tmp = heap.get(0);
		valueIndexMap.remove(tmp);
		valueKeyMap.remove(tmp);
		heap.set(0, heap.get(size() - 1));
		valueIndexMap.put(heap.get(0), 0);
		heap.remove(size() - 1);
		siftDown(0);
		return tmp;
	}

	/**
	 * Returns but not removes the minimal element of this binary heap.
	 * 
	 * @return the minimal element of the binary heap.
	 */
	public V getMin() {
		if (isEmpty()) {
			return null;
		}
		return heap.get(0);
	}
	
	/**
	 * Decreases key of the given element.
	 * 
	 * @param value
	 * @param newKey
	 * @throws NoSuchElementException -
	 *             if this binary heap does not contain <tt>value</tt>
	 * @throws IllegalArgumentException -
	 *             if the key to be replaced is less then the new one
	 */
	public void decreaseKey(V value, K newKey) {
		Integer tmp = valueIndexMap.get(value);//myData.indexOf(element);
		if (tmp == null) {
			throw new NoSuchElementException();
		}
		if (valueKeyMap.get(value).compareTo(newKey) < 0) {
			throw new IllegalArgumentException("The key replaced is less than the new one");
		}
		valueKeyMap.put(value, newKey);
		siftUp(tmp);
	}

	/**
	 * Increases key of the given element.
	 * 
	 * @param value
	 * @param newKey
	 * @throws NoSuchElementException -
	 *             if this binary heap does not contain <tt>value</tt>
	 * @throws IllegalArgumentException -
	 *             if the key to be replaced is greater then the new one
	 */
	public void increaseKey(V value, K newKey) {
		Integer tmp = valueIndexMap.get(value);//myData.indexOf(element);
		if (tmp == null) {
			throw new NoSuchElementException();
		}
		if (valueKeyMap.get(value).compareTo(newKey) >= 0) {
			throw new IllegalArgumentException("The key replaced is greater than the new one");
		}
		valueKeyMap.put(value, newKey);
		siftDown(tmp);
	}
	
	private void siftUp(int i) {
		int j = i;
		while ((j > 0) && (valueKeyMap.get(heap.get(j)).compareTo(valueKeyMap.get(heap.get(parent(j)))) < 0)) {
			swap(j, parent(j));
			j = parent(j);
		}
	}
	
	private void siftDown(int i) {
		int minIndex = getMinimalSon(i);
		if (minIndex == -1) {
			return;
		}
		if (valueKeyMap.get(heap.get(i)).compareTo(valueKeyMap.get(heap.get(minIndex))) > 0) {
			swap(i, minIndex);
			siftDown(minIndex);
		}
	}

	private int getMinimalSon(int i) {
		if (left(i) >= heap.size()) {
			return -1;
		}
		if (right(i) >= heap.size()) {
			return left(i);
		}
		return (valueKeyMap.get(heap.get(left(i))).compareTo(
				valueKeyMap.get(heap.get(right(i)))) <= 0) ? left(i) : right(i);
	}

	private void swap(int i, int j) {
		V temp = heap.get(i);
		valueIndexMap.put(heap.get(j), i);
		valueIndexMap.put(heap.get(i), j);
		heap.set(i, heap.get(j));
		heap.set(j, temp);
	}

	private int parent(int i) {
		return (i - 1) / 2;
	}

	private int left(int i) {
		return 2 * i + 1;
	}

	private int right(int i) {
		return 2 * i + 2;
	}

	@Override
	public String toString() {
		return heap.toString();
	}
}
